The present invention generally relates to apparatus and methods for coding and decoding digital data, and more particularly to an apparatus and method for efficiently decompressing entropy coded data.
Over the years, portable (or hand-held) game machines have been, and continue to be, very popular. Typically, these portable game machines include a hand-held game machine housing a display for displaying images and a game processing unit, and associated hardware for running a game program. The game program itself is typically contained in a game program memory such as, for example, a semiconductor memory (e.g., ROM, EPROM, etc.) that is part of a removable cartridge. By storing the game program in a removable cartridge, the user can conveniently and easily change the game being played by simply exchanging one cartridge with another, different cartridge containing a different game. Examples of portable game machines are the “Game Boy®” and “Game Boy® Color” products manufactured and sold by Nintendo of America Inc.
Generally, the functionality of conventional portable game machines of the type described above is directed to executing, on the hand-held processing unit, the game that is provided to the game program memory from a particular removable cartridge in response to user input. When using the portable game machine, visual and auditory feedback is provided to the user. The visual and auditory content is stored in compressed form in the removable cartridge along with programming information to instruct the processor for decompressing the content. The visual content is provided to the user on a color or monochrome display, such as a liquid crystal display (LCD), and the auditory content is provided from a speaker that is part of the hand-held unit or to a headphone jack.
A prior art embedded device is illustrated in FIGS. 1A, 1B, and 1C, which show a portable (hand-held) color display game machine (hereinafter, referred to simply as “game machine”) 10 that displays game characters in color on a color liquid crystal display (LCD) 16 when a prior art color-ready game cartridge 12 is selectively inserted into a slot 18′, and in FIG. 2 as an overall block diagram of the game machine and game cartridge. Batteries (not shown) (e.g., 2 AA batteries) provide power for game machine 10, which may also be configured for connection to an AC adapter to permit extended use without batteries. Game machine 10 is a prior art game machine and is described, for example, in U.S. Pat. No. 6,716,103, incorporated herein by reference.
The color LCD 16 displays either color or black and white depending on the type of game cartridge 12 inserted into the game machine 10. With reference to FIG. 2, prior art game machine 10 includes color LCD 16 as described above, and is formed as a dot matrix display and is driven by LCD drivers 22 and 24 to display color images on its screen. LCD driver 22 selectively drives, for example, the rows of the dot matrix display and LCD driver 24 selectively drives, for example, the columns of the dot matrix display. LCD drivers 22, 24 are supplied with color image signals from a color display processing circuit 28 included in a central processing unit (CPU) 25.
CPU 25 further includes a CPU core 30 that is connected to an internal read only memory (ROM) 32 and an internal random access memory (RAM) 34. Internal RAM 34 is used as a work memory of CPU core 30. CPU 25 further includes a basic oscillator 36, for example, a quartz oscillator that supplies an oscillating signal to a programmable frequency divider 38. Programmable frequency divider 38 divides the oscillating signal from basic oscillator 36 in accordance with frequency division data from CPU core 30, and supplies a divided signal as a clock of CPU core 30.
Programs for operating game machine 10 are provided through a connector 40 connected to CPU 25 by an appropriate bus. More specifically, game cartridge 12 shown in FIG. 1A is selectively attachable to connector 40. Game cartridge 12 is preferably in the form of a replaceable memory cartridge that can be inserted into slot 18 of game machine 10 and having a printed circuit board with a connector defining a number of electrical contacts. When game cartridge 12 is inserted into slot 18 of game machine 10, the cartridge electrical contacts mate with corresponding “edge connector” electrical contacts within game machine 10. This action electrically connects the printed circuit board to the electronics within game machine 10. In this example, the printed circuit board of game cartridge 12 at least includes a read-only memory (ROM) 42 and a read/write memory (e.g., SRAM) 46. ROM 42 stores instructions and other information pertaining to a particular video game. ROM 42 for one game cartridge 12 may, for example, contain instructions and other information for an adventure game while the ROM of another game cartridge 12 may contain instructions and other information for a car race game or an educational game, for example. To play a game, a user of game machine 10 need only plug the appropriate game cartridge into slot 18 of game machine 10 thereby connecting the cartridge's ROM 42 (and any other circuitry it may contain) to game machine 10. This enables the game machine circuitry to access information contained within ROM 42 (and read/write memory 46), which information controls the game machine to play the appropriate video game by displaying images and reproducing sound as specified under control of the ROM game program information. Read/write memory 46 is used to store data such as game backup data.
In accordance with the game program, character data supplied from game cartridge 12 and the controller data from operating keys 48a-48e, CPU 25 executes data processing and writes display data into a display RAM 52, using an extended RAM 50 when necessary. As a result of the data processing by CPU 25, pixels of color LCD 16 are controlled and sound signals are provided, through volume controls 54 and 56, to a speaker 58 and/or to an earphone jack 60. Color LCD 16 displays still or moving images, and sound signals output from speaker 58 and/or earphone jack 60 include game sound effects, voices and music.
Generally speaking, to use game machine 10 to play a game, a user selects a game cartridge 12 containing a desired video game, and inserts that game cartridge into slot 18 of game machine 10, thereby electrically connecting ROM 42 and other cartridge electronics to game machine 10. The user then operates a power switch 21 (see FIG. 1B) to turn on game machine 10 and operates operating keys 48a-48e to control video game play.
The gaming experience depends on the quality of the content provided to the user, where the quality includes the resolution of the display (both in pixel and color resolution), the tonal quality of the sound output, and how rapidly the output can change in response to the user's input. The memory and computational limitations of embedded devices, such as game machine 10, require that audio and video be stored in the removable memory unit, such as game cartridge 12, in compressed format which must be decompressed prior to being displayed.
The ability of embedded devices to play back compressed audio and video is limited by the memory and processing power of game machine 10, the memory of game cartridge 12, and the speed at which the game machine can read information from the game cartridge. Data compression has become an important and integral part of many computer systems and networks. In particular, compression is used for, but not limited to, the storage or transmission of digital representations of text, sound, still images, audio, and video. Data compression algorithms permit an increased amount of information that can be stored on a storage medium, enabling multimedia teleconferencing, and allowing the real-time display of video over the Internet.
The device or algorithm that compresses and/or decompresses the data is termed a “codec”. Typically the codec is embodied as instructions to a programmable computer. The compression or decompression of a codec can include any one of a number of algorithms including, but not limited to, data manipulations, transformations, predictions, string recognition and replacement, and look-up tables or trees.
Thus, for example, lossless compression of the digital data, which provides for perfect reproduction of compressed data, can be improved by applying two or more consecutive compression algorithms to the data, for example by applying an algorithm that searches for and replaces repeating data sequences in a more compact manner, followed by an entropy coding algorithm that categorizes data according to their frequency and replaces more frequently occurring strings with smaller strings. Once so compressed, the data may be reconstructed by reversing the order of the compression steps. An example of such a technique is found in the DEFLATE compression algorithm. (RFC 1951, DEFLATE Compressed Data Format Specification version 1.3, http://www.ietf.org/rfc/rfc1951.txt). DEFLATE uses Lempel-Ziv 1977 (LZ77) compression to reduce the number of bits required to store repeating strings, and then further compresses the data using, as an entropy coding algorithm, either fixed or dynamic Huffman coding.
Huffman coding, as used in DEFLATE, substitutes fixed size segments of data with a code of variable length (for example by replacing each byte of original data with a code having a size of from 1 to a maximum allowable size, such as 15 bits). The Huffman code (that is, data values and their corresponding binary codes) is either predetermined prior to compression (fixed Huffman coding) or is determined at the time of compression to optimize the code for a particular data set or stream (dynamic Huffman coding). In general, Huffman coded data is stored as a header containing information used to reconstruct the code, followed by the coded data. Upon receipt of Huffman coded data, the prior art provides for using information in the header to generate a binary tree for looking-up codes, followed by the use of the binary tree for decoding.
FIG. 4 is a table 400 that contains a particular Huffman code that is generated for use in a particular set or stream of data (not shown), where a first column 401 contains data to be coded (“Value”), a second column 403 is the Huffman code, or codeword, for each Value (“Code”), and a third column 405 is the length in bits of each Code (“LCodeLength”). Table 400 contains substitutions for 16 Values between 0 and 17 (from column 401), each of which has a Code (from column 403) having a length of from 2 to 7 bits (column 405). As is known in the art, a Huffman code is a binary code where the code length increases with decreasing code occurrence. Thus, for example, table 400 has been generated from a frequency distribution of values (not shown), with the most commonly occurring values having the shortest codes. Thus, for example, the most commonly occurring value is 12, which has a 2-bit long code of 00, and the least commonly occurring value is either 0 or 17, which each have a 7-bit code of 1111110 and 1111111, respectively.
Importantly, the Huffman code is a prefix code, and thus the value corresponding to the code is determined after the number of bits of the code is read. Thus, for example, the code 100, which is a 3-bit code corresponding to a value of 16, is not repeated as the first 3 bits of any code of equal or longer length in table 400. In addition, neither the first bit (1) nor the first two bits (10) are the first bits of any shorter code. With a prefix code, strings can be processed bit-by-bit until a code value is obtained, the order of the bits uniquely determines the code, irregardless of the code length.
In DEFLATE, Huffman codes are decoded using a binary tree parser. The tree is generated from the statistical table used for coding values, and the encoded symbol is reconstructed by parsing the code through the tree.
An example of a prior art Huffman decoding algorithms as implemented in DEFLATE can be understood with reference to FIG. 5, which contains a prior art binary tree 500 for decoding values coded using the code of table 400. Nodes of the tree 500 are points designated by either a circle or a square. A line segment connecting the nodes is called a “branch.” The node located in the highest position is called a “root” 501. Further, an under node 502 connected via a branch 503 to a certain node 504 is termed a “child” of the node 504. Conversely, the upper layer node 504 is referred to as a “parent” of the child node 502. A node having no child is called a “leaf,” and a unique symbol corresponds to each leaf. Further, the nodes excluding the leaves are referred to as “internal nodes,” and the number of branches from the root down to each node constitutes levels or layers. In the figure, all internal nodes are shown as circles and leaf nodes are displayed as squares.
When encoding by use of the code tree 500, a path extending from the root 501 down to a target leaf is outputted as a code. More specifically, the algorithm proceeds by reading one bit at a time and branching to the left if the bit is a 0 and to the right if the bit is a 1. For instance, in the code tree illustrated in FIG. 5, the code 11010 leads to a symbol value “4” that corresponds to a leaf node 505 by following a path from root 501 that branches right (represented by the first code bit, 1), right (represented by the second code bit, 1), left (represented by the third code bit, 0), right (represented by the fourth code bit, 1), and lastly left (represented by the fifth code bit, 0). For exemplary purposes, each layer corresponds to N cycles of the computer processor unit (CPU). The number of processing cycles required to look up a value in tree 500 can be from 1N to 7N depending on the code length, with 5N processing cycles required to obtain the value for code 11010.
According to the principles of Huffman coding, the selection of short codes for frequently occurring values (with a minimum size of 1-bit) and long codes for infrequently occurring values reduces the number of bits, for example, required to store information. While Huffman codewords can greatly reduce the memory allocation, the processing times required to achieve the enumerated process limits its utility. These limitations are especially applicable to systems possessing small processing reservoirs. Thus, for example, embedded devices require the periodic decompression of small amounts of data. If the requested amount of data requires decompressing from more than one deflate block, then the Huffman tree would need to be extracted in-between blocks, before any decompression of the actual data can begin. This will clearly add an important (unwanted) processor time overhead. If the time allocated by the application to the decompression task is too high, unexpected slowdowns might occur.
While the prior art use of codecs, such as those using Huffman codes, is effective, the required memory and processor speed is not within the capabilities of most resource-limited devices, such as cell phones, personal digital assistants, and hand held games. Thus there is a need in the art for a method and apparatus that results in compression at least as good as prior art codecs, but which can be rapidly executed on devices having limited resources. Such a method and apparatus should be easily implemented in embedded devices.